package com.hy;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

/**
 * Created With IntelliJ IDEA.
 * Descriptions:
 * User:Mr.Du
 * Date:2024/8/21
 * Time:10:29
 */
public class FindSubstring {

    /**
     * 在给定字符串中查找所有子串的起始索引，这些子串是由给定单词数组中的每个单词恰好连接一次形成的。
     *
     * @param s 需要被搜索的字符串
     * @param words 一个字符串数组，其中每个单词长度相同
     * @return 包含所有满足条件子串起始索引的列表。如果未找到符合条件的子串，则返回空列表。
     */
    public List<Integer> findSubstring(String s, String[] words) {
        List<Integer> res = new ArrayList<>();
        // 参数校验，若输入为空或单词数组为空，则直接返回空列表
        if (s == null || words == null || words.length == 0) return res;

        // 使用哈希映射记录每个单词出现的次数
        Map<String, Integer> mp = new HashMap<>();
        for(String w : words) mp.put(w, mp.getOrDefault(w, 0) + 1);

        // 计算相关变量，m为字符串长度，n为单词数组长度，r为单个单词长度
        int m = s.length(), n = words.length, r = words[0].length();

        // 遍历字符串，步长为一个单词长度，检查每个可能的起始位置
        for(int i = 0; i + n * r <= m; i++){
            // 初始化当前子串的哈希映射用于计数
            Map<String, Integer> cur = new HashMap<>();
            // 提取子串
            String sub = s.substring(i, i + n * r);

            // 按单词长度遍历子串，提取单词并更新当前子串的单词计数
            for(int j = 0; j < sub.length(); j += r){
                String t = sub.substring(j, j + r);
                // 若当前单词不在原始单词映射中，则跳出循环
                if(!mp.containsKey(t)) break;
                cur.put(t, cur.getOrDefault(t, 0) + 1);
            }

            // 检查当前子串的单词计数映射是否与原始映射相等，即所有单词均出现且次数相符
            if(cur.equals(mp)) res.add(i);
        }

        // 返回所有满足条件的起始索引列表
        return res;
    }


    public List<Integer> findSubstring1(String s, String[] words) {
        List<Integer> res = new ArrayList<>();
        Map<String, Integer> mp = new HashMap<>();
        for(String ss : words) mp.put(ss, mp.getOrDefault(ss, 0) + 1);
        int l = 0, r = 0, n = s.length(), m = words.length, len = words[0].length();
        Map<String, Integer> mp1 = new HashMap<>(mp);
        while(r < n){
            String str = s.substring(r, r + len);
            if(mp.containsKey(str) && mp.get(str) > 0){
                mp.put(str, mp.get(str) - 1);
                int cnt = 0;
                for(String ss : mp.keySet()){
                    if(mp.get(ss) == 0) cnt++;
                }
                if(cnt == mp.size()){
                    res.add(l);
                    mp = new HashMap<>(mp1);
                    l += len;
                    r = l;
                }else {
                    r += len;
                }
            }else{
                l += len;
                r = l;
                mp = new HashMap<>(mp1);
            }
        }
        return res;
    }

    public static void main(String[] args) {
        String s = "wordgoodgoodgoodbestword";
        String[] words = {"word", "good", "best", "word"};
        List<Integer> substring = new FindSubstring().findSubstring(s, words);
        System.out.println(substring);
    }

}
